package com.cn.algorithm02.class05;

import com.cn.algorithm02.class01.CodeUtil;

/***
 * @author: hels
 * @description: 递归和非递归方式实现归并排序
 **/
public class C01_MergeSort {
    public static void main(String[] args) {
        int[] arr = CodeUtil.generatorArray();
        process(arr);
        CodeUtil.printArray(arr);
    }

    public static void process(int[] arr, int L, int R) {
        // arr != null 不越界。。。
        // 1 base case
        if (L == R) return;

        // 2 递归分块
        int mid =  L + ((R - L) >> 1);
        process(arr, L, mid);
        process(arr, mid+1, R);
        // 3 核心逻辑
        merge(arr, L, mid, R);
    }

    private static void merge(int[] arr, int L, int mid, int R) {
        int p1 = L,p2 = mid+1; // 左右子模块指针
        int[] sortArr = new int[R-L+1];
        int index = 0;// 辅助数组指针

        while (p1 <= mid && p2 <= R) {
            sortArr[index++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
        //p1 和 p2 始终有一个指针没有遍历完
        while (p1 <= mid) {
            sortArr[index++] =  arr[p1++];
        }
        while (p2 <= R) {
            sortArr[index++] =  arr[p2++];
        }
        // copy element of sortArr to original source
        for (int i = 0; i < sortArr.length; i++) {
            arr[L++] = sortArr[i];
        }
    }

    // 使用非递归方式排序
    public static void process(int[] arr) {
        int step = 1;
        int len = arr.length;
        while (step < len) {
            int L = 0;
            while (L <= len - 1) {
                int mid = L + step - 1;
                if (mid >= len - 1) {
                    break;
                }

                int R = Math.min(mid+step, len-1);
                merge(arr, L, mid, R);
                L = R + 1;
            }
            if (step > len/2){
                break;
            }
            step <<= 1;
        }
    }

}
